package offerbook;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 按行打印BT，换行要打印空格
 * @date 2020/3/12 23:47
 */
public class Code60_LevelPrintTree {
    /**
     * 方式1：每次遍历一个节点要统计当前节点与上个节点的 树高是否变化，变化则打印换行。
     * 每次都要求节点高度，复杂度较大。
     */
    /**
     * 方式2：维护两个变量，当前行剩下要打印的数curPrint，下一行总个数nextPrint
     */
    public static void print(TreeNode root){
        if(root == null) return;
        int curPrint = 1;
        int nextPrint = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            // 注意这里一定要先判断，再出队！！可以用第一层走一次
            if(curPrint == 0){
                System.out.println();
                curPrint = nextPrint;
                nextPrint = 0;
            }
            root = queue.poll();
            curPrint--;
            System.out.print(root.val+"  ");
            if(root.left != null) {
                queue.offer(root.left);
                nextPrint++;
            }
            if(root.right != null) {
                queue.offer(root.right);
                nextPrint++;
            }
        }
    }

    //牛客

    public static ArrayList<ArrayList<Integer>> print2(TreeNode root){
        if(root == null) return new ArrayList<>();
        int curPrint = 1;
        int nextPrint = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //同一层要打印的
        ArrayList<Integer> sameHeightList = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //如果当前遍历到第二层，那么处理第一层的结果。
            // 注意这里一定要先判断，再出队！！可以用第一层走一次
            if(curPrint == 0){
                res.add(new ArrayList<>(sameHeightList));
                sameHeightList.clear();
                curPrint = nextPrint;
                nextPrint = 0;
            }
            root = queue.poll();
            curPrint -- ;
            sameHeightList.add(root.val);
            if(root.left != null) {
                queue.offer(root.left);
                nextPrint++;
            }
            if(root.right != null) {
                queue.offer(root.right);
                nextPrint++;
            }
        }
        //退出循环，但是最后一层结果还没处理
        res.add(new ArrayList<>(sameHeightList));
        return res;
    }
}
